Public Key Encryption, as utilised by applications like PGP, was invented by Whitfield Diffie and Martin Hellman in 1977. Another group of computer scientists later enhanced this system to work under prime number factorisation, and renamed it the RSA Cryptography System, after the three scientist's last names. This 'main' method of encryption involves prime numbers.
We all know about Prime Numbers - they are taught at schools world-wide. A prime number can't be divided evenly to produce an integer by any number other than itself, and 1. There are an infinite number of primes, and they follow no set pattern, other than that they are prime. When you multiple two primes together, you get a number that can only be divided evenly by those two primes. Example : 7 (prime) x 5 (prime) = 35. Only the numbers 7 and 5 can be divided into 35.
It's easy to multiply the two primes 11927 and 20903 to get 249310081 - but it's incredibly difficult to recover from this number the two primes that multiplied to make it. This is the basis of the most powerful, most sophisticated and ingenious system of encryption. It takes a huge amount of time for even the biggest computers to 'factor' a large product back to it's primes. Bearing in mind that the largest prime known to man has 895,932 digits in it, it will be a very long time before public key encryption can begin to be under threat from computers. (BTW, you can read about the longest prime number at http://www.utm.edu/research/primes/notes/2976221/)
Public Key Encryption utilises this fact to create two different decoding 'keys' - one to encipher a message and a different, but related, one to decipher it. The enciphering key is based on the product of two huge primes, whereas the deciphering key is based on the primes themselves. A computer can generate keys in a flash, as it's easy for a computer to generate primes and multiply them.
The three scientists responsible for inventing Public Key Encryption came 'under fire' from critics, as no-one really knew how secure was. They predicted that it would take millions of years to factor a 'simple' 130-digit number - as opposed to one with nearly 900,000 digits in!
To prove their point, they challenged the world to find the two factors responsible in this 129-digit number, known as the RSA-129.
They were entirely sure that their message (encrypted with the key) would be totally secure forever. In 1993 a group of more than 600 academics and hobbyists from around the world began a methodical 'assault' on the 129-digit number, using the Internet to co-ordinate various computers. In less than a year they factored the number into two primes, one 64 digits long, the other 65.
The encoded message read, "The magic words are squeamish and ossifrage."
The lesson to be learnt was that 129-digit keys were not long enough to protect really important and sensitive important. However, Increasing the key a few digits makes the key much more difficult to crack.
Mathematicians are quoted on saying that a 250-digit prime would take millions of years to factor with any foreseeable amount of computing power. They're probably right.
On to the hackers. In 1995, a cryptography consultant, Paul Kocher, was able to break a certain type of Public Key Encryption without any type of brute-force factorising. He timed the amount of time computers took to decode certain public keys, and used it against them. After only a few hundred tries, he narrowed down the public number to the one the computer used for encryption by timing the computer, and converting the time taken into a region of primes.
Public Key Encryption was simply updated so that this method would not work again, by using static times for encryption/decryption, although we never know when another stroke of genius will put the future of Public Key Encryption in doubt. There may be other ways of cracking it we haven't thought about yet. Also, mathematicians are hunting for a formula for the nth prime, which if found would also render PKE useless. For the moment, though, one thing we don't have to worry about is 'running out' of primes. There are far more primes of appropriate length than there are atoms in the universe, so the chance of duplicating an already found prime numbers' factors, or compiling a table, are also vanishingly small.
So, there you have it. Another idea like Paul Kocher's could give the owner a means to counterfeit money, penetrate any personal, corporate of government file, and possibly undermine the security of nations, take over small countries, that sort of thing.
